package likou.jindian;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2020/11/26 11:18
 */
public class _03_05 {
    int[] stack;
    int index = 0;
    int size = 8;

    public _03_05() {
        stack = new int[size];
    }

    public void push(int val) {
        if (index == size) {
            //扩容
            size = size << 1;
            int[] tmp = new int[size];
            System.arraycopy(stack, 0, tmp, 0, (size >> 1));
            stack = tmp;
        }
        //往下找，二分查找，找到之后，插入排序
        int search = search(val);
        if (index - search >= 0) {
            System.arraycopy(stack, search, stack, search + 1, index - search);
        }
        stack[search] = val;
        index++;

    }

    public void pop() {
        if (index > 0) {
            --index;
        }
    }

    public int peek() {
        if (index > 0) {
            return stack[index - 1];
        }
        return -1;
    }

    public boolean isEmpty() {
        return index == 0;
    }

    public int search(int val){
        if (index==0){
            return 0;
        }
        if(val>=stack[0]){
            return 0;
        }
        if(val<=stack[index-1]){
            return index;
        }
        int end = index-1;
        int start = 0;
        while(start<end){
            int mid = (start+end)/2;
            if (stack[mid]==val){
                return mid+1;
            }
            if(stack[mid]<val){
                end=mid-1;
            }
            if(stack[mid]>=val){
                start=mid+1;
            }
        }
        return start;
    }

    public static void main(String[] args) {
        _03_05 stack = new _03_05();
        stack.push(1);
        stack.push(2);
        stack.push(2);
        stack.push(3);
        stack.push(2);
        stack.push(1);
        stack.push(5);
        System.out.println(stack);
    }
}
